// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Reflection;
using System.Xml.Schema;
using System.Xml.XPath;
using System.Xml.Xsl;
using System.Xml.Xsl.Runtime;

namespace System.Xml.Xsl.Qil
{
    /// <summary>
    /// This class performs two functions:
    ///   1. Infer XmlQueryType of Qil nodes (constant, from arguments, etc)
    ///   2. Validate the arguments of Qil nodes if DEBUG is defined
    /// </summary>
    internal class QilTypeChecker
    {
        public QilTypeChecker()
        {
        }

        public XmlQueryType Check(QilNode n)
        {
            #region AUTOGENERATED
            return n.NodeType switch
            {
                QilNodeType.QilExpression => CheckQilExpression((QilExpression)n),
                QilNodeType.FunctionList => CheckFunctionList((QilList)n),
                QilNodeType.GlobalVariableList => CheckGlobalVariableList((QilList)n),
                QilNodeType.GlobalParameterList => CheckGlobalParameterList((QilList)n),
                QilNodeType.ActualParameterList => CheckActualParameterList((QilList)n),
                QilNodeType.FormalParameterList => CheckFormalParameterList((QilList)n),
                QilNodeType.SortKeyList => CheckSortKeyList((QilList)n),
                QilNodeType.BranchList => CheckBranchList((QilList)n),
                QilNodeType.OptimizeBarrier => CheckOptimizeBarrier((QilUnary)n),
                QilNodeType.Unknown => CheckUnknown(n),

                QilNodeType.DataSource => CheckDataSource((QilDataSource)n),
                QilNodeType.Nop => CheckNop((QilUnary)n),
                QilNodeType.Error => CheckError((QilUnary)n),
                QilNodeType.Warning => CheckWarning((QilUnary)n),

                QilNodeType.For => CheckFor((QilIterator)n),
                QilNodeType.Let => CheckLet((QilIterator)n),
                QilNodeType.Parameter => CheckParameter((QilParameter)n),
                QilNodeType.PositionOf => CheckPositionOf((QilUnary)n),

                QilNodeType.True => CheckTrue(n),
                QilNodeType.False => CheckFalse(n),
                QilNodeType.LiteralString => CheckLiteralString((QilLiteral)n),
                QilNodeType.LiteralInt32 => CheckLiteralInt32((QilLiteral)n),
                QilNodeType.LiteralInt64 => CheckLiteralInt64((QilLiteral)n),
                QilNodeType.LiteralDouble => CheckLiteralDouble((QilLiteral)n),
                QilNodeType.LiteralDecimal => CheckLiteralDecimal((QilLiteral)n),
                QilNodeType.LiteralQName => CheckLiteralQName((QilName)n),
                QilNodeType.LiteralType => CheckLiteralType((QilLiteral)n),
                QilNodeType.LiteralObject => CheckLiteralObject((QilLiteral)n),

                QilNodeType.And => CheckAnd((QilBinary)n),
                QilNodeType.Or => CheckOr((QilBinary)n),
                QilNodeType.Not => CheckNot((QilUnary)n),

                QilNodeType.Conditional => CheckConditional((QilTernary)n),
                QilNodeType.Choice => CheckChoice((QilChoice)n),

                QilNodeType.Length => CheckLength((QilUnary)n),
                QilNodeType.Sequence => CheckSequence((QilList)n),
                QilNodeType.Union => CheckUnion((QilBinary)n),
                QilNodeType.Intersection => CheckIntersection((QilBinary)n),
                QilNodeType.Difference => CheckDifference((QilBinary)n),
                QilNodeType.Average => CheckAverage((QilUnary)n),
                QilNodeType.Sum => CheckSum((QilUnary)n),
                QilNodeType.Minimum => CheckMinimum((QilUnary)n),
                QilNodeType.Maximum => CheckMaximum((QilUnary)n),

                QilNodeType.Negate => CheckNegate((QilUnary)n),
                QilNodeType.Add => CheckAdd((QilBinary)n),
                QilNodeType.Subtract => CheckSubtract((QilBinary)n),
                QilNodeType.Multiply => CheckMultiply((QilBinary)n),
                QilNodeType.Divide => CheckDivide((QilBinary)n),
                QilNodeType.Modulo => CheckModulo((QilBinary)n),

                QilNodeType.StrLength => CheckStrLength((QilUnary)n),
                QilNodeType.StrConcat => CheckStrConcat((QilStrConcat)n),
                QilNodeType.StrParseQName => CheckStrParseQName((QilBinary)n),

                QilNodeType.Ne => CheckNe((QilBinary)n),
                QilNodeType.Eq => CheckEq((QilBinary)n),
                QilNodeType.Gt => CheckGt((QilBinary)n),
                QilNodeType.Ge => CheckGe((QilBinary)n),
                QilNodeType.Lt => CheckLt((QilBinary)n),
                QilNodeType.Le => CheckLe((QilBinary)n),

                QilNodeType.Is => CheckIs((QilBinary)n),
                QilNodeType.After => CheckAfter((QilBinary)n),
                QilNodeType.Before => CheckBefore((QilBinary)n),

                QilNodeType.Loop => CheckLoop((QilLoop)n),
                QilNodeType.Filter => CheckFilter((QilLoop)n),

                QilNodeType.Sort => CheckSort((QilLoop)n),
                QilNodeType.SortKey => CheckSortKey((QilSortKey)n),
                QilNodeType.DocOrderDistinct => CheckDocOrderDistinct((QilUnary)n),

                QilNodeType.Function => CheckFunction((QilFunction)n),
                QilNodeType.Invoke => CheckInvoke((QilInvoke)n),

                QilNodeType.Content => CheckContent((QilUnary)n),
                QilNodeType.Attribute => CheckAttribute((QilBinary)n),
                QilNodeType.Parent => CheckParent((QilUnary)n),
                QilNodeType.Root => CheckRoot((QilUnary)n),
                QilNodeType.XmlContext => CheckXmlContext(n),
                QilNodeType.Descendant => CheckDescendant((QilUnary)n),
                QilNodeType.DescendantOrSelf => CheckDescendantOrSelf((QilUnary)n),
                QilNodeType.Ancestor => CheckAncestor((QilUnary)n),
                QilNodeType.AncestorOrSelf => CheckAncestorOrSelf((QilUnary)n),
                QilNodeType.Preceding => CheckPreceding((QilUnary)n),
                QilNodeType.FollowingSibling => CheckFollowingSibling((QilUnary)n),
                QilNodeType.PrecedingSibling => CheckPrecedingSibling((QilUnary)n),
                QilNodeType.NodeRange => CheckNodeRange((QilBinary)n),
                QilNodeType.Deref => CheckDeref((QilBinary)n),

                QilNodeType.ElementCtor => CheckElementCtor((QilBinary)n),
                QilNodeType.AttributeCtor => CheckAttributeCtor((QilBinary)n),
                QilNodeType.CommentCtor => CheckCommentCtor((QilUnary)n),
                QilNodeType.PICtor => CheckPICtor((QilBinary)n),
                QilNodeType.TextCtor => CheckTextCtor((QilUnary)n),
                QilNodeType.RawTextCtor => CheckRawTextCtor((QilUnary)n),
                QilNodeType.DocumentCtor => CheckDocumentCtor((QilUnary)n),
                QilNodeType.NamespaceDecl => CheckNamespaceDecl((QilBinary)n),
                QilNodeType.RtfCtor => CheckRtfCtor((QilBinary)n),

                QilNodeType.NameOf => CheckNameOf((QilUnary)n),
                QilNodeType.LocalNameOf => CheckLocalNameOf((QilUnary)n),
                QilNodeType.NamespaceUriOf => CheckNamespaceUriOf((QilUnary)n),
                QilNodeType.PrefixOf => CheckPrefixOf((QilUnary)n),

                QilNodeType.TypeAssert => CheckTypeAssert((QilTargetType)n),
                QilNodeType.IsType => CheckIsType((QilTargetType)n),
                QilNodeType.IsEmpty => CheckIsEmpty((QilUnary)n),

                QilNodeType.XPathNodeValue => CheckXPathNodeValue((QilUnary)n),
                QilNodeType.XPathFollowing => CheckXPathFollowing((QilUnary)n),
                QilNodeType.XPathPreceding => CheckXPathPreceding((QilUnary)n),
                QilNodeType.XPathNamespace => CheckXPathNamespace((QilUnary)n),

                QilNodeType.XsltGenerateId => CheckXsltGenerateId((QilUnary)n),
                QilNodeType.XsltInvokeLateBound => CheckXsltInvokeLateBound((QilInvokeLateBound)n),
                QilNodeType.XsltInvokeEarlyBound => CheckXsltInvokeEarlyBound((QilInvokeEarlyBound)n),
                QilNodeType.XsltCopy => CheckXsltCopy((QilBinary)n),
                QilNodeType.XsltCopyOf => CheckXsltCopyOf((QilUnary)n),
                QilNodeType.XsltConvert => CheckXsltConvert((QilTargetType)n),

                _ => CheckUnknown(n),
            };
            #endregion
        }

        #region meta
        //-----------------------------------------------
        // meta
        //-----------------------------------------------
        public XmlQueryType CheckQilExpression(QilExpression node)
        {
            Check(node[0].NodeType == QilNodeType.False || node[0].NodeType == QilNodeType.True, node, "IsDebug must either be True or False");
            CheckLiteralValue(node[1], typeof(XmlWriterSettings));
            CheckLiteralValue(node[2], typeof(IList<WhitespaceRule>));
            CheckClassAndNodeType(node[3], typeof(QilList), QilNodeType.GlobalParameterList);
            CheckClassAndNodeType(node[4], typeof(QilList), QilNodeType.GlobalVariableList);
            CheckLiteralValue(node[5], typeof(IList<EarlyBoundInfo>));
            CheckClassAndNodeType(node[6], typeof(QilList), QilNodeType.FunctionList);
            return XmlQueryTypeFactory.ItemS;
        }

        public XmlQueryType CheckFunctionList(QilList node)
        {
            foreach (QilNode child in node)
                CheckClassAndNodeType(child, typeof(QilFunction), QilNodeType.Function);
            return node.XmlType;
        }

        public XmlQueryType CheckGlobalVariableList(QilList node)
        {
            foreach (QilNode child in node)
                CheckClassAndNodeType(child, typeof(QilIterator), QilNodeType.Let);
            return node.XmlType;
        }

        public XmlQueryType CheckGlobalParameterList(QilList node)
        {
            foreach (QilNode child in node)
            {
                CheckClassAndNodeType(child, typeof(QilParameter), QilNodeType.Parameter);
                Check(((QilParameter)child).Name != null, child, "Global parameter's name is null");
            }
            return node.XmlType;
        }

        public XmlQueryType CheckActualParameterList(QilList node)
        {
            return node.XmlType;
        }

        public XmlQueryType CheckFormalParameterList(QilList node)
        {
            foreach (QilNode child in node)
                CheckClassAndNodeType(child, typeof(QilParameter), QilNodeType.Parameter);
            return node.XmlType;
        }

        public XmlQueryType CheckSortKeyList(QilList node)
        {
            foreach (QilNode child in node)
                CheckClassAndNodeType(child, typeof(QilSortKey), QilNodeType.SortKey);
            return node.XmlType;
        }

        public XmlQueryType CheckBranchList(QilList node)
        {
            return node.XmlType;
        }

        public XmlQueryType CheckOptimizeBarrier(QilUnary node)
        {
            return node.Child.XmlType;
        }

        public XmlQueryType CheckUnknown(QilNode node)
        {
            return node.XmlType;
        }

        #endregion // meta

        #region specials
        //-----------------------------------------------
        // specials
        //-----------------------------------------------
        public XmlQueryType CheckDataSource(QilDataSource node)
        {
            CheckXmlType(node.Name, XmlQueryTypeFactory.StringX);
            CheckXmlType(node.BaseUri, XmlQueryTypeFactory.StringX);
            return XmlQueryTypeFactory.NodeNotRtfQ;
        }

        public XmlQueryType CheckNop(QilUnary node)
        {
            return node.Child.XmlType;
        }

        public XmlQueryType CheckError(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.StringX);
            return XmlQueryTypeFactory.None;
        }

        public XmlQueryType CheckWarning(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.StringX);
            return XmlQueryTypeFactory.Empty;
        }

        #endregion // specials

        #region variables
        //-----------------------------------------------
        // variables
        //-----------------------------------------------
        public XmlQueryType CheckFor(QilIterator node)
        {
            return node.Binding.XmlType.Prime;
        }

        public XmlQueryType CheckLet(QilIterator node)
        {
            return node.Binding.XmlType;
        }

        public XmlQueryType CheckParameter(QilParameter node)
        {
            Check(node.Binding == null || node.Binding.XmlType.IsSubtypeOf(node.XmlType), node, "Parameter binding's xml type must be a subtype of the parameter's type");
            return node.XmlType;
        }

        public XmlQueryType CheckPositionOf(QilUnary node)
        {
            return XmlQueryTypeFactory.IntX;
        }

        #endregion // variables

        #region literals
        //-----------------------------------------------
        // literals
        //-----------------------------------------------
        public XmlQueryType CheckTrue(QilNode node)
        {
            return XmlQueryTypeFactory.BooleanX;
        }

        public XmlQueryType CheckFalse(QilNode node)
        {
            return XmlQueryTypeFactory.BooleanX;
        }

        public XmlQueryType CheckLiteralString(QilLiteral node)
        {
            CheckLiteralValue(node, typeof(string));
            return XmlQueryTypeFactory.StringX;
        }

        public XmlQueryType CheckLiteralInt32(QilLiteral node)
        {
            CheckLiteralValue(node, typeof(int));
            return XmlQueryTypeFactory.IntX;
        }

        public XmlQueryType CheckLiteralInt64(QilLiteral node)
        {
            CheckLiteralValue(node, typeof(long));
            return XmlQueryTypeFactory.IntegerX;
        }

        public XmlQueryType CheckLiteralDouble(QilLiteral node)
        {
            CheckLiteralValue(node, typeof(double));
            return XmlQueryTypeFactory.DoubleX;
        }

        public XmlQueryType CheckLiteralDecimal(QilLiteral node)
        {
            CheckLiteralValue(node, typeof(decimal));
            return XmlQueryTypeFactory.DecimalX;
        }

        public XmlQueryType CheckLiteralQName(QilName node)
        {
            CheckLiteralValue(node, typeof(QilName));
            // BUGBUG: Xslt constructs invalid QNames, so don't check this
            //Check(ValidateNames.ValidateName(node.Prefix, node.LocalName, node.NamespaceUri, XPathNodeType.Element, ValidateNames.Flags.All), node, "QName is not valid");
            return XmlQueryTypeFactory.QNameX;
        }

        public XmlQueryType CheckLiteralType(QilLiteral node)
        {
            CheckLiteralValue(node, typeof(XmlQueryType));
            return (XmlQueryType)node;
        }

        public XmlQueryType CheckLiteralObject(QilLiteral node)
        {
            Check(node.Value != null, node, "Literal value is null");
            return XmlQueryTypeFactory.ItemS;
        }

        #endregion // literals

        #region boolean operators
        //-----------------------------------------------
        // boolean operators
        //-----------------------------------------------
        public XmlQueryType CheckAnd(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.BooleanX);
            CheckXmlType(node.Right, XmlQueryTypeFactory.BooleanX);
            return XmlQueryTypeFactory.BooleanX;
        }

        public XmlQueryType CheckOr(QilBinary node)
        {
            return CheckAnd(node);
        }

        public XmlQueryType CheckNot(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.BooleanX);
            return XmlQueryTypeFactory.BooleanX;
        }

        #endregion // boolean operators

        #region choice
        //-----------------------------------------------
        // choice
        //-----------------------------------------------
        public XmlQueryType CheckConditional(QilTernary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.BooleanX);
            return XmlQueryTypeFactory.Choice(node.Center.XmlType, node.Right.XmlType);
        }

        public XmlQueryType CheckChoice(QilChoice node)
        {
            CheckXmlType(node.Expression, XmlQueryTypeFactory.IntX);
            CheckClassAndNodeType(node.Branches, typeof(QilList), QilNodeType.BranchList);
            Check(node.Branches.Count > 0, node, "Choice must have at least one branch");
            return node.Branches.XmlType;
        }

        #endregion // choice

        #region collection operators
        //-----------------------------------------------
        // collection operators
        //-----------------------------------------------
        public XmlQueryType CheckLength(QilUnary node)
        {
            return XmlQueryTypeFactory.IntX;
        }

        public XmlQueryType CheckSequence(QilList node)
        {
            return node.XmlType;
        }

        public XmlQueryType CheckUnion(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.NodeNotRtfS);
            CheckXmlType(node.Right, XmlQueryTypeFactory.NodeNotRtfS);
            return DistinctType(XmlQueryTypeFactory.Sequence(node.Left.XmlType, node.Right.XmlType));
        }

        public XmlQueryType CheckIntersection(QilBinary node)
        {
            return CheckUnion(node);
        }

        public XmlQueryType CheckDifference(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.NodeNotRtfS);
            CheckXmlType(node.Right, XmlQueryTypeFactory.NodeNotRtfS);
            return XmlQueryTypeFactory.AtMost(node.Left.XmlType, node.Left.XmlType.Cardinality);
        }

        public XmlQueryType CheckAverage(QilUnary node)
        {
            XmlQueryType xmlType = node.Child.XmlType;
            CheckNumericXS(node.Child);
            return XmlQueryTypeFactory.PrimeProduct(xmlType, xmlType.MaybeEmpty ? XmlQueryCardinality.ZeroOrOne : XmlQueryCardinality.One);
        }

        public XmlQueryType CheckSum(QilUnary node)
        {
            return CheckAverage(node);
        }

        public XmlQueryType CheckMinimum(QilUnary node)
        {
            return CheckAverage(node);
        }

        public XmlQueryType CheckMaximum(QilUnary node)
        {
            return CheckAverage(node);
        }

        #endregion // collection operators

        #region arithmetic operators
        //-----------------------------------------------
        // arithmetic operators
        //-----------------------------------------------
        public XmlQueryType CheckNegate(QilUnary node)
        {
            CheckNumericX(node.Child);
            return node.Child.XmlType;
        }

        public XmlQueryType CheckAdd(QilBinary node)
        {
            CheckNumericX(node.Left);
            CheckNumericX(node.Right);
            CheckNotDisjoint(node);
            return node.Left.XmlType.TypeCode == XmlTypeCode.None ? node.Right.XmlType : node.Left.XmlType;
        }

        public XmlQueryType CheckSubtract(QilBinary node)
        {
            return CheckAdd(node);
        }

        public XmlQueryType CheckMultiply(QilBinary node)
        {
            return CheckAdd(node);
        }

        public XmlQueryType CheckDivide(QilBinary node)
        {
            return CheckAdd(node);
        }

        public XmlQueryType CheckModulo(QilBinary node)
        {
            return CheckAdd(node);
        }

        #endregion // arithmetic operators

        #region string operators
        //-----------------------------------------------
        // string operators
        //-----------------------------------------------
        public XmlQueryType CheckStrLength(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.StringX);
            return XmlQueryTypeFactory.IntX;
        }

        public XmlQueryType CheckStrConcat(QilStrConcat node)
        {
            CheckXmlType(node.Delimiter, XmlQueryTypeFactory.StringX);
            CheckXmlType(node.Values, XmlQueryTypeFactory.StringXS);
            return XmlQueryTypeFactory.StringX;
        }

        public XmlQueryType CheckStrParseQName(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.StringX);
            Check(node.Right.XmlType.IsSubtypeOf(XmlQueryTypeFactory.StringX) || node.Right.XmlType.IsSubtypeOf(XmlQueryTypeFactory.NamespaceS),
                  node, "StrParseQName must take either a string or a list of namespace as its second argument");
            return XmlQueryTypeFactory.QNameX;
        }

        #endregion // string operators

        #region value comparison operators
        //-----------------------------------------------
        // value comparison operators
        //-----------------------------------------------
        public XmlQueryType CheckNe(QilBinary node)
        {
            CheckAtomicX(node.Left);
            CheckAtomicX(node.Right);
            CheckNotDisjoint(node);
            return XmlQueryTypeFactory.BooleanX;
        }

        public XmlQueryType CheckEq(QilBinary node)
        {
            return CheckNe(node);
        }

        public XmlQueryType CheckGt(QilBinary node)
        {
            return CheckNe(node);
        }

        public XmlQueryType CheckGe(QilBinary node)
        {
            return CheckNe(node);
        }

        public XmlQueryType CheckLt(QilBinary node)
        {
            return CheckNe(node);
        }

        public XmlQueryType CheckLe(QilBinary node)
        {
            return CheckNe(node);
        }

        #endregion // value comparison operators

        #region node comparison operators
        //-----------------------------------------------
        // node comparison operators
        //-----------------------------------------------
        public XmlQueryType CheckIs(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.NodeNotRtf);
            CheckXmlType(node.Right, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.BooleanX;
        }

        public XmlQueryType CheckAfter(QilBinary node)
        {
            return CheckIs(node);
        }

        public XmlQueryType CheckBefore(QilBinary node)
        {
            return CheckIs(node);
        }

        #endregion // node comparison operators

        #region loops
        //-----------------------------------------------
        // loops
        //-----------------------------------------------
        public XmlQueryType CheckLoop(QilLoop node)
        {
            CheckClass(node[0], typeof(QilIterator));
            Check(node.Variable.NodeType == QilNodeType.For || node.Variable.NodeType == QilNodeType.Let, node, "Loop variable must be a For or Let iterator");

            XmlQueryType bodyType = node.Body.XmlType;
            XmlQueryCardinality variableCard = node.Variable.NodeType == QilNodeType.Let ? XmlQueryCardinality.One : node.Variable.Binding.XmlType.Cardinality;

            // Loops do not preserve DocOrderDistinct
            return XmlQueryTypeFactory.PrimeProduct(bodyType, variableCard * bodyType.Cardinality);
        }

        public XmlQueryType CheckFilter(QilLoop node)
        {
            CheckClass(node[0], typeof(QilIterator));
            Check(node.Variable.NodeType == QilNodeType.For || node.Variable.NodeType == QilNodeType.Let, node, "Filter variable must be a For or Let iterator");
            CheckXmlType(node.Body, XmlQueryTypeFactory.BooleanX);

            // Attempt to restrict filter's type by checking condition
            XmlQueryType filterType = FindFilterType(node.Variable, node.Body);
            if (filterType != null)
                return filterType;

            return XmlQueryTypeFactory.AtMost(node.Variable.Binding.XmlType, node.Variable.Binding.XmlType.Cardinality);
        }

        #endregion // loops

        #region sorting
        //-----------------------------------------------
        // sorting
        //-----------------------------------------------
        public XmlQueryType CheckSort(QilLoop node)
        {
            XmlQueryType varType = node.Variable.Binding.XmlType;

            CheckClassAndNodeType(node[0], typeof(QilIterator), QilNodeType.For);
            CheckClassAndNodeType(node[1], typeof(QilList), QilNodeType.SortKeyList);

            // Sort does not preserve DocOrderDistinct
            return XmlQueryTypeFactory.PrimeProduct(varType, varType.Cardinality);
        }

        public XmlQueryType CheckSortKey(QilSortKey node)
        {
            CheckAtomicX(node.Key);
            CheckXmlType(node.Collation, XmlQueryTypeFactory.StringX);
            return node.Key.XmlType;
        }

        public XmlQueryType CheckDocOrderDistinct(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtfS);
            return DistinctType(node.Child.XmlType);
        }

        #endregion // sorting

        #region function definition and invocation
        //-----------------------------------------------
        // function definition and invocation
        //-----------------------------------------------
        public XmlQueryType CheckFunction(QilFunction node)
        {
            CheckClassAndNodeType(node[0], typeof(QilList), QilNodeType.FormalParameterList);
            Check(node[2].NodeType == QilNodeType.False || node[2].NodeType == QilNodeType.True, node, "SideEffects must either be True or False");
            Check(node.Definition.XmlType.IsSubtypeOf(node.XmlType), node, "Function definition's xml type must be a subtype of the function's return type");
            return node.XmlType;
        }

        public XmlQueryType CheckInvoke(QilInvoke node)
        {
#if DEBUG
            CheckClassAndNodeType(node[1], typeof(QilList), QilNodeType.ActualParameterList);

            QilList actualArgs = node.Arguments;
            QilList formalArgs = node.Function.Arguments;
            Check(actualArgs.Count == formalArgs.Count, actualArgs, "Invoke argument count must match function's argument count");

            for (int i = 0; i < actualArgs.Count; i++)
                Check(actualArgs[i].XmlType.IsSubtypeOf(formalArgs[i].XmlType), actualArgs[i], "Invoke argument must be a subtype of the invoked function's argument");
#endif

            return node.Function.XmlType;
        }

        #endregion // function definition and invocation

        #region XML navigation
        //-----------------------------------------------
        // XML navigation
        //-----------------------------------------------
        public XmlQueryType CheckContent(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.AttributeOrContentS;
        }

        public XmlQueryType CheckAttribute(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.NodeNotRtf);
            CheckXmlType(node.Right, XmlQueryTypeFactory.QNameX);
            return XmlQueryTypeFactory.AttributeQ;
        }

        public XmlQueryType CheckParent(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.DocumentOrElementQ;
        }

        public XmlQueryType CheckRoot(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.NodeNotRtf;
        }

        public XmlQueryType CheckXmlContext(QilNode node)
        {
            return XmlQueryTypeFactory.NodeNotRtf;
        }

        public XmlQueryType CheckDescendant(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.ContentS;
        }

        public XmlQueryType CheckDescendantOrSelf(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.Choice(node.Child.XmlType, XmlQueryTypeFactory.ContentS);
        }

        public XmlQueryType CheckAncestor(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.DocumentOrElementS;
        }

        public XmlQueryType CheckAncestorOrSelf(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.Choice(node.Child.XmlType, XmlQueryTypeFactory.DocumentOrElementS);
        }

        public XmlQueryType CheckPreceding(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.DocumentOrContentS;
        }

        public XmlQueryType CheckFollowingSibling(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.ContentS;
        }

        public XmlQueryType CheckPrecedingSibling(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.ContentS;
        }

        public XmlQueryType CheckNodeRange(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.NodeNotRtf);
            CheckXmlType(node.Right, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.Choice(node.Left.XmlType, XmlQueryTypeFactory.ContentS, node.Right.XmlType);
        }

        public XmlQueryType CheckDeref(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.NodeNotRtf);
            CheckXmlType(node.Right, XmlQueryTypeFactory.StringX);
            return XmlQueryTypeFactory.ElementS;
        }

        #endregion // XML navigation

        #region XML construction
        //-----------------------------------------------
        // XML construction
        //-----------------------------------------------
        public XmlQueryType CheckElementCtor(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.QNameX);
            CheckXmlType(node.Right, XmlQueryTypeFactory.NodeNotRtfS);
            return XmlQueryTypeFactory.UntypedElement;
        }

        public XmlQueryType CheckAttributeCtor(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.QNameX);
            CheckXmlType(node.Right, XmlQueryTypeFactory.NodeNotRtfS);
            return XmlQueryTypeFactory.UntypedAttribute;
        }

        public XmlQueryType CheckCommentCtor(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtfS);
            return XmlQueryTypeFactory.Comment;
        }

        public XmlQueryType CheckPICtor(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.StringX);
            CheckXmlType(node.Right, XmlQueryTypeFactory.NodeNotRtfS);
            return XmlQueryTypeFactory.PI;
        }

        public XmlQueryType CheckTextCtor(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.StringX);
            return XmlQueryTypeFactory.Text;
        }

        public XmlQueryType CheckRawTextCtor(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.StringX);
            return XmlQueryTypeFactory.Text;
        }

        public XmlQueryType CheckDocumentCtor(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtfS);
            return XmlQueryTypeFactory.UntypedDocument;
        }

        public XmlQueryType CheckNamespaceDecl(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.StringX);
            CheckXmlType(node.Right, XmlQueryTypeFactory.StringX);
            return XmlQueryTypeFactory.Namespace;
        }

        public XmlQueryType CheckRtfCtor(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.NodeNotRtfS);
            CheckClassAndNodeType(node.Right, typeof(QilLiteral), QilNodeType.LiteralString);
            return XmlQueryTypeFactory.Node;
        }

        #endregion // XML construction

        #region Node properties
        //-----------------------------------------------
        // Node properties
        //-----------------------------------------------
        public XmlQueryType CheckNameOf(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.Node);
            return XmlQueryTypeFactory.QNameX;
        }

        public XmlQueryType CheckLocalNameOf(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.Node);
            return XmlQueryTypeFactory.StringX;
        }

        public XmlQueryType CheckNamespaceUriOf(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.Node);
            return XmlQueryTypeFactory.StringX;
        }

        public XmlQueryType CheckPrefixOf(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.Node);
            return XmlQueryTypeFactory.StringX;
        }

        #endregion // Node properties
        #region Copy operators

        #endregion // Copy operators

        #region Type operators
        //-----------------------------------------------
        // Type operators
        //-----------------------------------------------
        public XmlQueryType CheckTypeAssert(QilTargetType node)
        {
            CheckClassAndNodeType(node[1], typeof(QilLiteral), QilNodeType.LiteralType);
            return node.TargetType;
        }

        public XmlQueryType CheckIsType(QilTargetType node)
        {
            CheckClassAndNodeType(node[1], typeof(QilLiteral), QilNodeType.LiteralType);
            return XmlQueryTypeFactory.BooleanX;
        }

        public XmlQueryType CheckIsEmpty(QilUnary node)
        {
            return XmlQueryTypeFactory.BooleanX;
        }

        #endregion // Type operators

        #region XPath operators
        //-----------------------------------------------
        // XPath operators
        //-----------------------------------------------
        public XmlQueryType CheckXPathNodeValue(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeS);
            return XmlQueryTypeFactory.StringX;
        }

        public XmlQueryType CheckXPathFollowing(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.ContentS;
        }

        public XmlQueryType CheckXPathPreceding(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.ContentS;
        }

        public XmlQueryType CheckXPathNamespace(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtf);
            return XmlQueryTypeFactory.NamespaceS;
        }

        #endregion // XPath operators

        #region XSLT
        //-----------------------------------------------
        // XSLT
        //-----------------------------------------------
        public XmlQueryType CheckXsltGenerateId(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.NodeNotRtfS);
            return XmlQueryTypeFactory.StringX;
        }

        public XmlQueryType CheckXsltInvokeLateBound(QilInvokeLateBound node)
        {
            CheckLiteralValue(node[0], typeof(QilName));
            CheckClassAndNodeType(node[1], typeof(QilList), QilNodeType.ActualParameterList);
            return XmlQueryTypeFactory.ItemS;
        }

        public XmlQueryType CheckXsltInvokeEarlyBound(QilInvokeEarlyBound node)
        {
#if DEBUG
            CheckLiteralValue(node[0], typeof(QilName));
            CheckLiteralValue(node[1], typeof(MethodInfo));
            CheckClassAndNodeType(node[2], typeof(QilList), QilNodeType.ActualParameterList);

            XmlExtensionFunction extFunc = new XmlExtensionFunction(node.Name.LocalName, node.Name.NamespaceUri, node.ClrMethod);
            QilList actualArgs = node.Arguments;
            Check(actualArgs.Count == extFunc.Method.GetParameters().Length, actualArgs, "InvokeEarlyBound argument count must match function's argument count");

            for (int i = 0; i < actualArgs.Count; i++)
            {
                Check(actualArgs[i].XmlType.IsSubtypeOf(extFunc.GetXmlArgumentType(i)), actualArgs[i], "InvokeEarlyBound argument must be a subtype of the invoked function's argument type");
            }
#endif

            return node.XmlType;
        }

        public XmlQueryType CheckXsltCopy(QilBinary node)
        {
            CheckXmlType(node.Left, XmlQueryTypeFactory.NodeNotRtf);
            CheckXmlType(node.Right, XmlQueryTypeFactory.NodeS);
            return XmlQueryTypeFactory.Choice(node.Left.XmlType, node.Right.XmlType);
        }

        public XmlQueryType CheckXsltCopyOf(QilUnary node)
        {
            CheckXmlType(node.Child, XmlQueryTypeFactory.Node);

            if ((node.Child.XmlType.NodeKinds & XmlNodeKindFlags.Document) != 0)
                return XmlQueryTypeFactory.NodeNotRtfS;

            return node.Child.XmlType;
        }

        public XmlQueryType CheckXsltConvert(QilTargetType node)
        {
            CheckClassAndNodeType(node[1], typeof(QilLiteral), QilNodeType.LiteralType);
            return node.TargetType;
        }
        #endregion // Xslt operators


        //-----------------------------------------------
        // Helper functions
        //-----------------------------------------------

        [Conditional("DEBUG")]
        private void Check(bool value, QilNode node, string message)
        {
            if (!value)
                QilValidationVisitor.SetError(node, message);
        }

        [Conditional("DEBUG")]
        private void CheckLiteralValue(QilNode node, Type clrTypeValue)
        {
            Check(node is QilLiteral, node, "Node must be instance of QilLiteral");

            Type clrType = ((QilLiteral)node).Value.GetType();
            Check(clrTypeValue.IsAssignableFrom(clrType), node, "Literal value must be of type " + clrTypeValue.Name);
        }

        [Conditional("DEBUG")]
        private void CheckClass(QilNode node, Type clrTypeClass)
        {
            Check(clrTypeClass.IsAssignableFrom(node.GetType()), node, "Node must be instance of " + clrTypeClass.Name);
        }

        [Conditional("DEBUG")]
        private void CheckClassAndNodeType(QilNode node, Type clrTypeClass, QilNodeType nodeType)
        {
            CheckClass(node, clrTypeClass);
            Check(node.NodeType == nodeType, node, "Node must have QilNodeType." + nodeType);
        }

        [Conditional("DEBUG")]
        private void CheckXmlType(QilNode node, XmlQueryType xmlType)
        {
            Check(node.XmlType.IsSubtypeOf(xmlType), node, "Node's type " + node.XmlType + " is not a subtype of " + xmlType);
        }

        [Conditional("DEBUG")]
        private void CheckNumericX(QilNode node)
        {
            Check(node.XmlType.IsNumeric && node.XmlType.IsSingleton && node.XmlType.IsStrict, node, "Node's type " + node.XmlType + " must be a strict singleton numeric type");
        }

        [Conditional("DEBUG")]
        private void CheckNumericXS(QilNode node)
        {
            Check(node.XmlType.IsNumeric && node.XmlType.IsStrict, node, "Node's type " + node.XmlType + " must be a strict numeric type");
        }

        [Conditional("DEBUG")]
        private void CheckAtomicX(QilNode node)
        {
            Check(node.XmlType.IsAtomicValue && node.XmlType.IsStrict, node, "Node's type " + node.XmlType + " must be a strict atomic value type");
        }

        [Conditional("DEBUG")]
        private void CheckNotDisjoint(QilBinary node)
        {
            Check(node.Left.XmlType.IsSubtypeOf(node.Right.XmlType) || node.Right.XmlType.IsSubtypeOf(node.Left.XmlType), node,
                  "Node must not have arguments with disjoint types " + node.Left.XmlType + " and " + node.Right.XmlType);
        }

        private XmlQueryType DistinctType(XmlQueryType type)
        {
            if (type.Cardinality == XmlQueryCardinality.More)
                return XmlQueryTypeFactory.PrimeProduct(type, XmlQueryCardinality.OneOrMore);

            if (type.Cardinality == XmlQueryCardinality.NotOne)
                return XmlQueryTypeFactory.PrimeProduct(type, XmlQueryCardinality.ZeroOrMore);

            return type;
        }

        private XmlQueryType FindFilterType(QilIterator variable, QilNode body)
        {
            XmlQueryType leftType;
            QilBinary binary;

            if (body.XmlType.TypeCode == XmlTypeCode.None)
                return XmlQueryTypeFactory.None;

            switch (body.NodeType)
            {
                case QilNodeType.False:
                    return XmlQueryTypeFactory.Empty;

                case QilNodeType.IsType:
                    // If testing the type of "variable", then filter type can be restricted
                    if ((object)((QilTargetType)body).Source == (object)variable)
                        return XmlQueryTypeFactory.AtMost(((QilTargetType)body).TargetType, variable.Binding.XmlType.Cardinality);
                    break;

                case QilNodeType.And:
                    // Both And conditions can be used to restrict filter's type
                    leftType = FindFilterType(variable, ((QilBinary)body).Left);
                    if (leftType != null)
                        return leftType;

                    return FindFilterType(variable, ((QilBinary)body).Right);

                case QilNodeType.Eq:
                    // Restrict cardinality if position($iterator) = $pos is found
                    binary = (QilBinary)body;
                    if (binary.Left.NodeType == QilNodeType.PositionOf)
                    {
                        if ((object)((QilUnary)binary.Left).Child == (object)variable)
                            return XmlQueryTypeFactory.AtMost(variable.Binding.XmlType, XmlQueryCardinality.ZeroOrOne);
                    }
                    break;
            }

            return null;
        }
    }
}
